import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import org.junit.Test;

public class MyTest {
    public List<Integer> pathInZigZagTree(int label) {
        List<Integer> ans=new ArrayList<Integer>();
        int n=1;
        int depth=1;
        while(n<<1<=label){
            depth++;
            n<<=1;
        }
        if(depth%2==0){
            label=getReverse(label, depth);
        }
        while(depth>0){
            if(depth%2==0){
                ans.add(getReverse(label, depth));
            }else{
                ans.add(label);
            }
            depth--;
            label>>=1;
        }
        Collections.reverse(ans);
        return ans;
    }   
    private int getReverse(int label,int depth){
        return (1<<depth)-label-1+(1<<depth-1);
    }

    public int search(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        int mid=(left+right)/2;
        while(left<=right){
            if(target==nums[mid]){
                return mid;
            }
            if(nums[0]<=nums[mid]){
                if(target<nums[mid]&&target>=nums[0]){
                    right=mid-1;
                }else{
                    left=mid+1;
                }
            }else{
                if(target>nums[mid]&&target<=nums[nums.length-1]){
                    left=mid+1;
                }else{
                    right=mid-1;
                }
            }
            mid=(left+right)/2;
        }
        return -1;
    }

    @Test
    public void test(){
        int[] nums={4,5,6,7,8,1,2,3};
        int target=8;
        System.out.println(search(nums, target));
    }
}
